#include<stdio.h>
#include<malloc.h>
#include<string.h>

//3.1 图结构体实现
#define MAXSIZE 3
#define ZERO 0
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int NODE[MAXSIZE][MAXSIZE];
typedef int STATUS;


typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE* next;       //领进节点
}NEIGHBORNODE, * NEIGHBOR;             //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】

typedef struct ANODE                 //节点类型
{
    NODE node;                       //节点
    NEIGHBOR adjacents;              //邻近节点
}ANYNODE;                            //节点类型【将ANODE重命名为ANYNODE】

typedef struct GRAPHNODE             //图的节点的存储类型
{
    ANYNODE node;                    //节点
    struct GRAPHNODE* next;          //其他节点
}GRAPHNODE, * GRAPH;                   //图类型【*GRAPH为指向GRAPHNODE的指针】

typedef struct NEIGHBORNODE* PATH;   //路径类型

typedef struct Paths                 //路径集合类型
{
    PATH path;                       //一条路径
    struct Paths* next;              //下一条路径
}Paths, * PATHS;                       //路径集合类型【*PATHS为指向PATH的指针】

typedef struct Paths* STACK;                //定义堆栈类型，实际上也是节点链表【相邻节点链表】

//3.2.2 通用赋值函数
void Set(NODE node1, NODE node2)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            node1[i][j] = node2[i][j];
        }
    }
}

//3.7.1 判断两个九宫格是否相同、赋值
STATUS equal(NODE node1, NODE node2)
{
    int i, j;
    STATUS flag = TRUE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node1[i][j] != node2[i][j])
            {
                flag = FALSE;
                return 1;
                break;
            }
        }
        if (flag == FALSE)   break;
    }
    return 0;
}


//3.7.2 显示九宫格
void PriNode(NODE node)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)  printf("%5d", node[i][j]);
        printf("\n");
    }
    printf("****************\n");
}

void PriPath(PATH path)                     //显示路径
{
    while (path!= NULL)
    {
        PriNode(path->node);
        path = path->next;
    }
    printf("\n");
    //priNeighbors((NEIGHBOR)path);             //路径与兄弟节点集合形式相同
}

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br, NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b, pb;                                  //相邻节点
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    Set(b->node, node);             //【下面两行是类型为str时的情况，其他类比】
    b->next = NULL;
    if (br == NULL)                                    //没有相邻节点的情况
    {
        br = b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb = br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while (pb->next)   pb = pb->next;
        pb->next = b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.4 双亲与子节点关系的构建
GRAPH Form_Pa_Ch(NODE pa, NEIGHBOR br)                 //将相邻节点(所有子节点)链接到双亲节点中，构成一个子树
{
    GRAPH graph;
    graph = (GRAPH)malloc(sizeof(struct GRAPHNODE));   //创建双亲节点
    Set(br->node, pa);
    graph->next = NULL;
    graph->node.adjacents = br;                        //相邻节点与双亲节点构成子图
    return graph;                                    //返回带相邻节点的双亲结点，即子图
}

//3.2.5 将带子节点的双亲节点加入到图中
GRAPH Add_A_Sub_Graph(GRAPH graph, GRAPH subgraph) //将双亲结点加入到图中
{
    GRAPH t = graph;                        //临时图
    if (graph == NULL)                       //图不存在
    {
        graph = subgraph;                   //带子节点的双亲节点即为图
    }
    else                                  //图存在
    {
        while (t->next)  t = t->next;
        t->next = subgraph;                 //带子节点的双亲节点加入到图的最后
    }
    return graph;                         //返回图指针
}//graph是链式队列，通过上述程序实现子图subgraph(相邻结点)进队列过程

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1 = br;                 //临时相邻变量
    while (br)                        //【遍历相邻节点】
    {
        br1 = br;
        br = br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.2.7 清空图并回收数据单元
GRAPH ClearGraph(GRAPH graph)
{
    GRAPH graph1 = graph;              //临时图
    while (graph)                     //【遍历双亲节点】
    {
        graph1 = graph;
        graph = graph->next;          //【挨个变量赋给临时指针】
        free(graph1);               //回收单元
    }
    return graph;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//3.2.8 字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(相邻节点)的字符串
void CreateStr(char* neighborset)  //字符数组转换为多个字符串
{
    char* c = neighborset;           //临时字符串
    while (*c)
    {
        if (*c == '/')  *c = '\0';     //插入字符串结束标志
        c++;
    }
    c++;
    *c = '\0';                      //多一个结束标记
}

//3.3 图可复用代码部分
//3.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents)                       //节点集复制
{
    NEIGHBOR copynode=NULL, lastnode=NULL, head = NULL;                        //没有子节点
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(copynode->node, adjacents->node);
        copynode->next = NULL;
        if (head == NULL)
        {
            head = copynode;                                       //第1个节点
        }
        else
        {
            lastnode->next = copynode;                             //非第1个节点：建立链接，复制子节点集
        }
        lastnode = copynode;
        adjacents = adjacents->next;                               //下一个子节点
    }
    return head;                                                 //返回头节点指针
}

//3.3.2 复制路径和路径集合
PATH CopyPath(PATH path)                               //复制一条路径，返回新路径
{
    PATH tempath;
    tempath = (PATH)CopyNeighbors((NEIGHBOR)path);       //路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths)                     //复制路径集合
{
    PATHS copynode=NULL, lastnode=NULL, head = NULL;
    while (paths)                                 //路径集合不为空
    {
        copynode = (PATHS)malloc(sizeof(Paths));   //路径节点
        copynode->path = CopyPath(paths->path);    //复制一条路径
        copynode->next = NULL;                     //复制路径初始化
        if (head == NULL)                           //第1条路径
        {
            head = copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next = copynode;
        }
        lastnode = copynode;                       //加入路径集合
        paths = paths->next;
    }
    return head;
}

//3.3.3 节点加入路径
PATH Add_A_Node_To_Path(NODE node, PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p = (NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    Set(p->node, node);
    if (path == NULL)                            //第1个节点
    {
        p->next = NULL;
    }
    else                                      //非第1个节点
    {
        p->next = path;                         //加入到路径头部
    }
    path = p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//3.3.4 路径加入路径集合
PATHS Add_A_Path_To_Paths(PATH path, PATHS paths) //路径加入到路径集合中
{
    PATH copypath;
    PATHS ps = NULL, p;
    if (path == NULL)   return paths;                //没有路径
    copypath = CopyPath(path);                      //复制路径
    ps = (PATHS)malloc(sizeof(Paths));              //开辟路径集合节点
    ps->path = copypath;                            //复制的路径置入
    ps->next = NULL;
    if (paths == NULL)                               //路径集合为空
    {
        paths = ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p = paths;
        while (p->next) p = p->next;
        p->next = ps;
    }
    return paths;
}

//3.3.5 路径进栈和所有节点进栈
PATHS Push_A_Path(PATHS stack, PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    PATHS st;
    tempath = CopyPath(path);                            //复制节点
    st = (PATHS)malloc(sizeof(Paths));                   //路径节点
    st->path = tempath;                                  //置路径于栈中
    if (stack == NULL)                                    //第1条路径
    {
        st->next = stack;
    }
    else                                               //非第1条路径，已有路径
    {
        st->next = stack;
    }
    stack = st;
    return stack;
}

PATHS PushPaths(PATHS stack, PATHS paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS p, head;
    head = CopyPaths(paths);                           //复制路径集合
    p = head;
    if (p != NULL)                                      //逐一加入栈中
    {
        while (p->next) p = p->next;
        p->next = stack;
        stack = head;
    }
    return stack;
}

//3.3.6 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack)              //回收栈空间
{
    stack = (STACK)ClearNeighbors((NEIGHBOR)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path = (PATH)ClearNeighbors((NEIGHBOR)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths)               //回收路径集合空间
{
    PATHS paths1 = paths;
    while (paths)                              //所有路径
    {
        paths1 = paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths = paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//3.3.7 出栈与节点
PATHS Pop_A_Node(STACK stack, NODE node, PATH* path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    PATHS p = stack;
    PATH tempath;
    if (p != NULL)
    {
        tempath = p->path;                                //一条路径
        Set(node, tempath->node);
        *path = CopyPath(tempath);                         //获取路径
        stack = p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return stack;                                       //返回栈顶
}

//3.3.8 扩展节点集//UPDATE:更新的ExpandNodes

//3.3.9 路径倒叙与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num = 0, i;
    NODE* nodes;
    PATH p = path;
    while (p)                                //统计路径节点的个数
    {
        p = p->next;
        num++;
    }
    nodes = (NODE*)malloc(num * sizeof(NODE)); //开辟一维数组
    for (i = 0, p = path; p; p = p->next, i++)         //读取路径节点置于数组中
    {
        Set(nodes[i], p->node);
    }
    for (i = num - 1, p = path; p; p = p->next, i--)     //数组数据倒序置于路径中
    {
        Set(p->node, nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

//3.4 图求解路径实现
//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node, PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p = path;
    STATUS flag = FALSE;                                    //节点是否在路径中的标识
    while (p)
    {
        if (equal(node, p->node) == 0)                       //node在路径中
        {
            flag = TRUE;
            break;
        }
        else                                              //node不在路径中
        {
            p = p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.4.2 删除在路径中的节点
NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path)    //从节点集合adjacents中删除节点在路径path中的节点
{
    NEIGHBOR n1 = adjacents, n2=NULL;
    STATUS flag = FALSE;
    while (n1)                                              //遍历节点集合中的每个节点
    {
        flag = IsInPath(n1->node, path);                      //节点是否在路径中
        if (flag == TRUE)
        {
            if (n1 == adjacents)                              //待删除节点位于第一个
            {
                adjacents = n1->next;                        //下一个节点
                free(n1);                                  //删除当前节点
                n1 = adjacents;                              //其他节点
            }
            else                                           //待删除节点不在第一个
            {
                n2->next = n1->next;                         //NULL
                free(n1);                                  //删除当前节点
                n1 = n2->next;                               //NULL
            }
        }
        else
        {
            n2 = n1;                                          //下一个节点
            n1 = n1->next;
        }
    }
    return adjacents;
}

//3.4.3  相邻节点形成路径合集
PATHS FromPathsFromNodes(NEIGHBOR adjacents, PATH path, PATHS paths)   //节点集合中的每个节点（不在路径中）挨个加入路径，依次形成路径集合
{
    PATH tempath;
    adjacents = DeleteNodeInPath(adjacents, path);           //删除构成回路的节点
    while (adjacents)                                      //所有不构成回路的节点
    {
        tempath = CopyPath(path);                              //复制路径
        tempath = Add_A_Node_To_Path(adjacents->node, tempath); //在路径中加入一个节点
        paths = Add_A_Path_To_Paths(tempath, paths);            //新路径加入路径集合
        adjacents = adjacents->next;                           //下一个节点
    }
    return(paths);                                        //返回路径集合
}

//3.7.3 九宫格的空格交换
STATUS Locate(NODE node, int* hori, int* vert, int zero)
{
    int i, j;
    STATUS flag = FALSE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node[i][j] == zero)
            {
                *hori = i;
                *vert = j;
                flag = TRUE;
                break;
            }
        }
        if (flag == TRUE)   break;
    }
    return flag;
}

void Exchange(NODE node, int hori1, int vert1, int hori2, int vert2)
{
    int tempnode;
    tempnode = node[hori1][vert1];
    node[hori1][vert1] = node[hori2][vert2];
    node[hori2][vert2] = tempnode;
}

//3.7.4 相邻节点集合的生成
NEIGHBOR ExpandNodes(NODE node, int zero)
{
    NEIGHBOR adjacents = NULL;
    int h, v;
    NODE tempnode;
    if (!Locate(node, &h, &v, zero))     return adjacents;
    if (h == 0 && v == 0)                                       //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 2)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 0)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 0)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 1)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    return adjacents;
}

//3.7.0 路径搜索[DFS-九宫格改进版]
STATUS SearchPath(NODE start, NODE end, PATH* path, int target)   //判断节点是否在图中，并获取路径
{
    NODE node;
    NEIGHBOR adjacents;
    STACK stack = NULL;
    STATUS flag = FALSE;
    PATH tempath = NULL;
    PATHS paths = NULL;
    tempath = Add_A_Node_To_Path(start, tempath);                 //初始节点形成路径
    stack = Push_A_Path(stack, tempath);                          //路径进栈
    while (stack)                                               //任意一条路径
    {
        tempath = ClearPath(tempath);                            //清空路径
        stack = Pop_A_Node(stack, node, &tempath);                 //出栈
        if (equal(node, end) == 0)                                //目标节点
        {
            flag = TRUE;                                         //找到目标节点
            *path = CopyPath(tempath);                           //获取路径
            break;
        }
        adjacents = ExpandNodes(node, target);                    //相邻的所有节点
        paths = FromPathsFromNodes(adjacents, tempath, paths);     //形成不带回路的路径集合
        stack = PushPaths(stack, paths);                          //所有路径进栈
        paths = ClearPaths(paths);                               //回收所有路径
    }
    ClearStack(stack);                                         //清空堆栈
    return(flag);
}


//3.7.5 长度计算
long int LengthOfPath(PATH path)
{
    long int count=1;
    while(path!=NULL)
    {
        path = path->next;
        count++;
    }
    return count;
}

//3.7.M 主程序
int main()
{
    STACK stack = NULL;
    PATH path = NULL;
    STATUS flag;
    //NODE start={{2,8,3},{1,0,4},{7,6,5}},end={{1,2,3},{8,0,4},{7,6,5}};
    NODE start = {{1,2,3},{8,4,0},{7,6,5} }, end = {{1,2,3},{8,0,4},{7,6,5}};
    printf("Search from:\n");
    PriNode(start);
    printf("to:\n");
    PriNode(end);
    flag = SearchPath(start, end, &path, ZERO);
    printf("Path:\n");
    RevPath(path);
    PriPath(path);
    printf("\nStep=%ld,Status=%d\n", LengthOfPath(path) - 1, flag);
    printf("=============\n");
    ClearPath(path);
    return 0;
}